import numpy as np

class TicTacToe:
    def __init__(self):
        self.board = np.zeros((3, 3))  # 0表示空位，1表示X，-1表示O
        self.human = 1    # 玩家使用X
        self.ai = -1      # AI使用O
        
    def available_moves(self):
        """返回所有可用的位置"""
        moves = []
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == 0:
                    moves.append((i, j))
        return moves
    
    def make_move(self, position, player):
        """在指定位置放置棋子"""
        if self.board[position] == 0:
            self.board[position] = player
            return True
        return False
    
    def undo_move(self, position):
        """撤销移动"""
        self.board[position] = 0
        
    def check_winner(self):
        """检查是否有获胜者"""
        # 检查行
        for i in range(3):
            if sum(self.board[i, :]) == 3:
                return 1
            if sum(self.board[i, :]) == -3:
                return -1
                
        # 检查列
        for i in range(3):
            if sum(self.board[:, i]) == 3:
                return 1
            if sum(self.board[:, i]) == -3:
                return -1
                
        # 检查对角线
        if (self.board[0, 0] + self.board[1, 1] + self.board[2, 2] == 3 or
            self.board[0, 2] + self.board[1, 1] + self.board[2, 0] == 3):
            return 1
        if (self.board[0, 0] + self.board[1, 1] + self.board[2, 2] == -3 or
            self.board[0, 2] + self.board[1, 1] + self.board[2, 0] == -3):
            return -1
            
        # 检查是否平局
        if len(self.available_moves()) == 0:
            return 0
            
        # 游戏未结束
        return None
        
    def minimax(self, depth, is_maximizing):
        """极小化极大算法"""
        result = self.check_winner()
        
        if result is not None:
            return result
            
        if is_maximizing:
            best_score = float('-inf')
            for move in self.available_moves():
                self.make_move(move, self.human)
                score = self.minimax(depth + 1, False)
                self.undo_move(move)
                best_score = max(score, best_score)
            return best_score
        else:
            best_score = float('inf')
            for move in self.available_moves():
                self.make_move(move, self.ai)
                score = self.minimax(depth + 1, True)
                self.undo_move(move)
                best_score = min(score, best_score)
            return best_score
            
    def get_best_move(self):
        """获取AI的最佳移动"""
        best_score = float('inf')
        best_move = None
        
        for move in self.available_moves():
            self.make_move(move, self.ai)
            score = self.minimax(0, True)
            self.undo_move(move)
            
            if score < best_score:
                best_score = score
                best_move = move
                
        return best_move
        
    def print_board(self):
        """打印棋盘"""
        symbols = {1: 'X', -1: 'O', 0: ' '}
        for i in range(3):
            print('-------------')
            out = '| '
            for j in range(3):
                out += symbols[self.board[i, j]] + ' | '
            print(out)
        print('-------------')